package arithmetic.LeetCode;


import org.junit.jupiter.api.Test;

import utils.TreeNode;

/**
 * 124. 二叉树中的最大路径和
 * 二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
 * 路径和 是路径中各节点值的总和。
 * <p>
 * 给你一个二叉树的根节点 root ，返回其最大路径和 。
 * <p>
 * 输入：root = [1,2,3]
 * 输出：6
 * 解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6
 * <p>
 * https://leetcode.cn/problems/binary-tree-maximum-path-sum/
 *
 * @author jiangfeng on 2023/4/11
 */
public class BinTreeMaxPathSum {

    @Test
    public void test(){
        TreeNode tree = TreeNode.createTree(new Integer[] {-10, 9, 20, null, null, 15, 7});
        System.out.println(TreeNode.printTree(tree));
    }
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     * int val;
     * TreeNode left;
     * TreeNode right;
     * TreeNode() {}
     * TreeNode(int val) { this.val = val; }
     * TreeNode(int val, TreeNode left, TreeNode right) {
     * this.val = val;
     * this.left = left;
     * this.right = right;
     * }
     * }
     */
    // 动态规划, 子问题:
    // 以n为根节点,子序路径的最大值是: n节点的值+ 左子节点的到叶子节点最大值 + 右子节点叶子节点最大值
    // pb[n] = node[n] + (node[n-1左])+max:{}
    // 注意找出这其中的最大值.  注意一个变量,递归覆盖的问题.
    public int maxPathSum(TreeNode root) {
        int[] result = new int[] {Integer.MIN_VALUE};
        // 遍历一下,留一个最大值;
        maxPathSumNode(root, result);
        return result[0];
    }

    public int maxPathSumNode(TreeNode root, int[] result) {
        if (root == null) {
            return 0;
        }
        int left = Math.max(maxPathSumNode(root.left, result), 0);
        int right = Math.max(maxPathSumNode(root.right, result), 0);
        result[0] = Math.max(result[0], root.val + left + right);
        return root.val + Math.max(left, right);
    }


}
